#define _CRT_SECURE_NO_WARNINGS 1
//头文件
//design by lwh
#include<graphics.h>
#include<conio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<fstream>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<unordered_map>
#include<bitset>
#include<string>
#include<vector>
#include<easyx.h>
#include<cmath>
#include<ctime>

using namespace std;

typedef pair<int, int>PII;
typedef pair<int, PII>PIII;
//迷宫分辨率
#define WIDTH 720
#define HEIGHT 600
//迷宫内各点属性
#define ROAD 1
#define WALL 0
#define WAIT 2
#define FINISH 3
#define START 4

const int N = 1010,M = 1e5+10;//最大迷宫限制以及迷宫路径展示最大限制

// 定义一个结构体ExMessage，所有字段初始化为0
ExMessage msg = { 0 };

/*A*算法的时间复杂度为O(b^d)，其中b是分支因子（每个节点的子节点数量的平均值），d是从起始节点到目标节点的最短路径长度*/
int BLOCK_WIDTH, BLOCK_HEIGHT, BLOCK_XY;
map<int, int> lowlist[N];//最短路集合
map<int, int> alllist[N];//所有路径集合
map<int, int> li[N];//所有路径集合
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
int dist[N][N];//距离数组
bool st[N][N];//A*算法的去重数组
bool vis[N][N];//dfs算法的去重数组
int endx, endy;//终点坐标
int sax, say;//起点坐标
PII pre[N][N];//用于A*记录某个点是从哪个点来的
PII preD[N][N];//用于dfs记录某个点是从哪个点来的
map<int, int> S[N];//查重
RECT r = { 880, 250, 1310, 710 };//输出文本框
string word;//输出文本
int pathcount;//路径个数
bool ispt;//是否输出路径
bool isfind;//是否点击这个按钮
string tempword;//备份word数组
bool isdoneb12;//按了b12

// 定义一个Block结构体，包含整型字段x和y，使用构造函数初始化
class Block {
public:
	int x, y;
	Block(int x, int y) : x(x), y(y) {}
};

// 定义一个结构体E，用于A*算法的优先队列，包含字段f（启发值）、r（实际值）、x和y坐标
struct E {
	int f, r, x, y;

	// 重载小于运算符，用于优先队列，按照f值降序排序
	bool operator<(const E& t) const {
		return f > t.f;
	}
};

// 定义并查集类UnionFind，支持并查集操作
class UnionFind {
public:
	vector<int> p;   // 父节点数组

	// 构造函数，初始化并查集，包括父节点和秩数组
	UnionFind(int n) {
		if (p.size()) {
			p.clear();
		}
		p.resize(n + 1);
		for (int i = 1; i <= n; i++) {
			p[i] = i; // 每个节点初始时为自己的父节点
		}
	}

	// 查找操作，带路径压缩
	int find(int x) {
		if (x != p[x]) p[x] = find(p[x]); // 路径压缩
		return p[x];
	}

	// 合并操作，用于合并两个集合
	void merge(int a, int b) {
		int pa = find(a), pb = find(b);
		if (pa != pb) {
			p[pa] = pb; 
		}
	}

	// 判断两个元素是否属于同一集合
	bool issame(int a, int b) {
		return find(a) == find(b);
	}
};

// 定义text类，封装文本绘制参数
class text {
private:
	char a[1000]; // 文本存储数组
	int x, y;     // 坐标

public:
	// 构造函数，初始化坐标并复制文本到数组a
	text(int x, int y, char c[]) : x(x), y(y) {
		memcpy(a, c, sizeof a); // 复制文本到数组a
	}

	// 设置并绘制文本在指定坐标上
	void set() {
		outtextxy(x, y, a); // 假设outtextxy函数在其他地方定义
	}
};
//定义按钮类
class Button {
private:
	int x, y, w, h;
	char text[10000];
public:
	Button(int x, int y, int w, int h, const char* t):x(x), y(y), w(w), h(h) {

		memcpy(text, t, sizeof text); // 复制文本到数组a
	
	}

	//mx,my是否在指定的矩形区域
	bool inArea(int mx, int my, int x, int y, int w, int h) {
		return (mx > x && mx< x + w && my >y && my < y + h);
	}

	bool button() {

		//按钮变颜色
		if (inArea(msg.x, msg.y, x, y, w, h)) {
			setfillcolor(RGB(230, 231, 232));
		}
		else {
			setfillcolor(WHITE);
		}
		//绘制按钮
		fillroundrect(x, y, x + w, y + h, 5, 5);

		int cx, cy;

		cx = (w - textwidth(text)) / 2;
		cy = (h - textheight(text)) / 2;

		settextcolor(BLACK);
		outtextxy(x + cx, y + cy, text);

		if (msg.message == WM_LBUTTONDOWN && inArea(msg.x, msg.y, x, y, w, h)) {//左键按下且鼠标在按钮上
			return true;
		}
		return false;
	}
};


class Map {
private:
	int w[N][N];//原数组
	int g[N][N];//备份数组
public:
	Map() {}
	// 从二维数组g中获取位置(x, y)处的值
	int getg(int x, int y) {
		return g[x][y];
	}

	// 从二维数组w中获取位置(x, y)处的值
	int getw(int x, int y) {
		return w[x][y];
	}

	// 将二维数组w中位置(x, y)的值设置为k
	void setw(int x, int y, int k) {
		w[x][y] = k;
	}

	// 将数组w的内容复制到数组g中（假设g和w是大小相同的二维数组）
	void copy() {
		memcpy(g, w, sizeof w);
	}

	// 根据块指针A获取一个线性索引，假设BLOCK_WIDTH是一个常量宽度
	// 假设A表示一个具有x和y坐标的块
	// 根据BLOCK_WIDTH将二维坐标(x, y)转换为一维线性索引
	int get(Block* A) {
		return A->x + A->y * (BLOCK_WIDTH);
	}


	void change(int x, int y) {
		vector<Block*> lis;
		//上
		if (y - 2 >= 1 && w[x][y - 2] == ROAD) {
			Block* a = new Block(x, y - 1);
			lis.push_back(a);
		}
		//下
		if (y + 2 <= BLOCK_HEIGHT && w[x][y + 2] == ROAD) {
			Block* b = new Block(x, y + 1);
			lis.push_back(b);
		}
		//左
		if (x - 2 >= 1 && w[x - 2][y] == ROAD) {
			Block* c = new Block(x - 1, y);
			lis.push_back(c);
		}
		//右
		if (x + 2 <= BLOCK_WIDTH && w[x + 2][y] == ROAD) {
			Block* d = new Block(x + 1, y);
			lis.push_back(d);
		}
		if (lis.size() != 0) {//当lis不为0
			int BIndexea = rand() % lis.size();//随机找一个，把该位置设成路
			Block* B = lis[BIndexea];
			w[B->x][B->y] = ROAD;
		}
	}

	void kruskal() {
		// 创建边列表
		vector<pair<int, pair<Block*, Block*>>> edges;

		// 添加所有可能的边到边列表中
		for (int y = 1; y <= BLOCK_HEIGHT; y += 2) {
			for (int x = 1; x <= BLOCK_WIDTH; x += 2) {
				if (x - 2 >= 1) {
					edges.push_back({ rand(), { new Block(x, y), new Block(x - 2, y) } });
				}
				if (x + 2 <= BLOCK_WIDTH) {
					edges.push_back({ rand(), { new Block(x, y), new Block(x + 2, y) } });
				}
				if (y - 2 >= 1) {
					edges.push_back({ rand(), { new Block(x, y), new Block(x, y - 2) } });
				}
				if (y + 2 <= BLOCK_HEIGHT) {
					edges.push_back({ rand(), { new Block(x, y), new Block(x, y + 2) } });
				}
			}
		}

		// 随机打乱边列表
		random_shuffle(edges.begin(), edges.end());

		// 并查集数据结构来管理集合
		UnionFind uf(BLOCK_WIDTH * BLOCK_HEIGHT + 40);

		// 处理每条边
		for (auto edge : edges) {
			Block* A = edge.second.first;
			Block* B = edge.second.second;
			if (!uf.issame(get(A), get(B))) {
				/*将A与它四周一个随机已经变成路的路点打通*/
				w[A->x][A->y] = ROAD;
				change(A->x, A->y);

				w[B->x][B->y] = ROAD;
				change(B->x, B->y);
				jiaru(A->x, A->y);

				uf.merge(get(A), get(B));
				FlushBatchDraw();
				display();
			}
		}
		display();
	}

	void jiaru(int x, int y) {
		//上
		if (y - 2 >= 1 && w[x][y - 2] == WALL) {
			Block* a = new Block(x, y - 2);
			w[x][y - 2] = ROAD;
		}
		//下
		if (y + 2 <= BLOCK_HEIGHT && w[x][y + 2] == WALL) {
			Block* b = new Block(x, y + 2);
			w[x][y + 2] = ROAD;
		}
		//左
		if (x - 2 >= 1 && w[x - 2][y] == WALL) {
			Block* c = new Block(x - 2, y);
			w[x - 2][y] = ROAD;
		}
		//右
		if (x + 2 <= BLOCK_WIDTH && w[x + 2][y] == WALL) {
			Block* d = new Block(x + 2, y);
			w[x + 2][y] = ROAD;
		}
	}

	void init() {
		//初始化迷宫
		memset(w, WALL, sizeof w);
		//随机一点变成路
		int x = rand() % BLOCK_WIDTH + 1, y = rand() % BLOCK_HEIGHT + 1;
		w[x][y] = ROAD;
		/*将路点四周不是路的路点加入待选列表*/
		jiaru(x, y);
		//绘制迷宫=>制图
		kruskal();

	}

	//展示函数
	void display() {
		int cnt = 0; // 计数器初始化
		int cnt1 = 0; // 计数器初始化
		for (int i = 1; i <= BLOCK_WIDTH + 1; i++) { // 循环遍历每个网格块的列
			for (int j = 0; j <= BLOCK_HEIGHT; j++) { // 循环遍历每个网格块的行
				if (i == BLOCK_WIDTH + 1) { // 如果是为了做数字标记
					cnt++; // 计数加一
					if (j == BLOCK_HEIGHT) continue; // 如果是最后一行，继续下一次循环
					RECT c = { i * BLOCK_XY + 1, (j + 1) * BLOCK_XY + 1, BLOCK_XY + i * BLOCK_XY + 10, BLOCK_XY + (j + 1) * BLOCK_XY + 10 }; // 设置矩形区域
					string d = to_string(cnt); // 将计数转换为字符串
					char f[N] = { 0 }; // 字符数组初始化
					for (int k = 0; k < d.size(); k++) {
						f[k] = d[k]; // 将字符串复制到字符数组中
					}
					f[d.size()] = 0; // 添加字符串结束符
					drawtext(f, &c, DT_WORDBREAK | DT_CENTER); // 调用绘制文本函数显示数字标记
				}
				else if (j == 0) { // 如果是为了做数字标记
					cnt1++; // 计数加一
					RECT c = { i * BLOCK_XY + 1, j * BLOCK_XY + 1, BLOCK_XY + i * BLOCK_XY + 10, BLOCK_XY + j * BLOCK_XY + 10 }; // 设置矩形区域
					string d = to_string(cnt1); // 将计数转换为字符串
					char f[N] = { 0 }; // 字符数组初始化
					for (int k = 0; k < d.size(); k++) {
						f[k] = d[k]; // 将字符串复制到字符数组中
					}
					f[d.size()] = 0; // 添加字符串结束符
					drawtext(f, &c, DT_WORDBREAK | DT_CENTER | DT_BOTTOM); // 调用绘制文本函数显示数字标记
				}
				else { // 如果不是用来做数字标记
					if (w[i][j] == WALL) { // 如果是墙壁
						draw(i, j, BLACK); // 绘制黑色
					}
					else if (w[i][j] == FINISH) { // 如果是终点
						draw(i, j, DARKGRAY); // 绘制深灰色
					}
					else if (w[i][j] == START) { // 如果是起点
						draw(i, j, RED); // 绘制红色
					}
					else if (w[i][j] == ROAD && lowlist[i][j]) { // 如果是路径且用于DFS
						draw(i, j, CYAN); // 绘制青色
					}
					else if (w[i][j] == ROAD && alllist[i][j]) { // 如果是路径且用于A*算法
						draw(i, j, BROWN); // 绘制深灰色
					}
					else if (w[i][j] == ROAD) { // 如果是普通路径
						draw(i, j, WHITE); // 绘制白色
					}
				}
			}
		}
		FlushBatchDraw(); // 刷新批处理绘图
	}

	void display2() {
		for (int i = 1; i <= BLOCK_WIDTH; i++) { // 循环遍历每个网格块的列
			for (int j = 1; j <= BLOCK_HEIGHT; j++) { // 循环遍历每个网格块的行
				if (w[i][j] == WALL) { // 如果是墙壁
					draw(i, j, BLACK); // 绘制黑色
				}
				else if (w[i][j] == FINISH) { // 如果是终点
					draw(i, j, DARKGRAY); // 绘制深灰色
				}
				else if (w[i][j] == START) { // 如果是起点
					draw(i, j, RED); // 绘制红色
				}
				else if (w[i][j] == ROAD && li[i][j]) { // 如果是路径且用于DFS
					draw(i, j, YELLOW); // 绘制黄色
				}
				else if (w[i][j] == ROAD) { // 如果是普通路径
					draw(i, j, WHITE); // 绘制白色
				}
			}
		}
		FlushBatchDraw(); // 刷新批处理绘图
	}
	void wd() {

		string a;
		time_t t = time(NULL); // 获取当前时间戳

		// 将时间戳转换为struct tm结构体，可以得到年、月、日等时间信息
		struct tm* now = localtime(&t);

		// 从struct tm结构体中获取时和分
		int hour = now->tm_hour;
		int min = now->tm_min;
		a = to_string(BLOCK_WIDTH);
		a += "x";
		a += to_string(BLOCK_HEIGHT);
		a += " ";
		a += to_string(hour);
		a += ".";
		a += to_string(min);
		a += " map.txt";
		cout << a << endl;
		ofstream p(a, ios::out);

		p << BLOCK_WIDTH << " " << BLOCK_HEIGHT << " " << BLOCK_XY << endl;

		for (int i = 1; i <= BLOCK_WIDTH; i++) {
			for (int j = 1; j <= BLOCK_HEIGHT; j++) {
				if (w[i][j] == START||w[i][j] == FINISH) {
					p << ROAD << " ";
				}else {
					p << w[i][j] << ' ';
				}
			}
			p << endl;
		}
		p << endl;
		HWND hwn = GetHWnd();
		MessageBox(hwn, "导出成功", "提示", MB_OKCANCEL);
		p.close();
	}
	// 从文件中读入内容
	void rd(char c[]) {
		string a;

		// 将字符数组转换为字符串
		for (int i = 0; i < strlen(c); i++) {
			a += c[i];
		}

		// 打开文件流，读取文件内容
		ifstream p(a, ios::in);
		if (!p.is_open()) {     
			HWND hwn = GetHWnd();
			MessageBox(hwn, "不存在该文件", "警告", MB_OKCANCEL);
			return;
		}
		int n, m, k;
		p >> n >> m >> k;
		BLOCK_WIDTH = n, BLOCK_HEIGHT = m;

		BLOCK_XY = k;

		cout << n << " " << m << endl;

		// 读取二维数组w的内容
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				p >> w[i][j];
			}
		}

		// 将w数组复制给g数组
		memcpy(g, w, sizeof w);
		HWND hwn = GetHWnd();
		MessageBox(hwn, "导入成功", "提示", MB_OKCANCEL);
		p.close();
	}
	void draw(int x, int y, COLORREF RGB) {
		setfillcolor(RGB); // 设置填充颜色
		setlinecolor(COLORREF RGB(0, 0, 0)); // 设置线条颜色
		fillrectangle(x * BLOCK_XY, y * BLOCK_XY, BLOCK_XY + x * BLOCK_XY, BLOCK_XY + y * BLOCK_XY); // 绘制填充矩形
	}
};

struct Param
{
	int x, y, w, h;
};

//函数
int f(int sx, int sy, int ex, int ey);//估价函数
int A_start(int sx, int sy, int ex, int ey);//A*函数求最短路径
void dfs(int sx, int sy);//dfs求所有路径，时间复杂度是指数级别的
void print(int s, int t, bool f,bool isbutton);//A*或dfs路径打印与保存
void setButton(int x, int y, int W, int h);//按钮
Map w;//全局变量


/// <summary>
/// 主函数
/// </summary>
/// <returns></returns>
int main() {
	srand((unsigned)time(NULL));//随机数种子
	initgraph(1312, 720);//创建绘图窗口

	setbkcolor(WHITE);//设置背景色：白色

	cleardevice();//清空显示
	//按钮
	setButton(915, 20, 115, 35);//防止按钮

	getchar();

	return 0;
}

void setButton(int x, int y, int W, int h) {//w是宽度，h是高度
	// 设置线条颜色为黑色
	setlinecolor(BLACK);
	// 绘制一个矩形，坐标为(890, 0)到(1300, 520)
	

	// 字符串数组，表示不同的选项
	string p[N] = { "自动寻找所有路", "自动寻找最优路" };

	int i = -1; // 初始化变量 i 为 -1
	bool ff = false; // 判断是否生成了迷宫的标志

	while (1) { // 无限循环
		rectangle(860, 0, 1300, 715);
		peekmessage(&msg, EX_MOUSE); // 获取鼠标信息
		BeginBatchDraw(); // 开始批量绘制

		char a[N] = "路径 "; // 字符数组初始化为 "路径 "
		int q = strlen(a); // 获取数组 a 的长度

		if (i != -1) { // 如果 i 不等于 -1
			for (int k = 0; k < p[i].size(); k++) {
				a[q++] = p[i][k]; // 将选项 p[i] 的字符逐个添加到数组 a 中
			}
		}
		a[q] = 0; // 添加字符串结尾的空字符

		char b[] = "设计：lwh"; // 字符数组初始化为 "设计：lwh"

		// 创建文本对象 t1 和 t3
		text t1(1050, 200, a); // 在位置 (1050, 200) 创建文本对象 t1，内容为数组 a
		text t3(0, 710, b); // 在位置 (0, 540) 创建文本对象 t3，内容为数组 b

		t1.set(); // 设置文本 t1
		t3.set(); // 设置文本 t3

		// 创建按钮对象
		Button b1(x, y, W, h, "自动生成");
		Button b2(1045, 20, 115, 35, "文件导入");
		Button b3(915, 60, 115, 35, "自动寻找所有路");
		Button b4(1045, 60, 115, 35, "自动寻找最优路");
		Button b5(915, 100, 115, 35, "起点坐标设置");
		Button b6(1045, 100, 115, 35, "终点坐标设置");
		Button b7(915, 140, 115, 35, "清空还原");
		Button b8(1045, 140, 115, 35, "手动生成");
		Button b9(1170, 20, 115, 35, "保存迷宫");
		Button b10(1170, 60, 115, 35, "查看路径");
		Button b11(1170, 100, 115, 35, "直接展示");
		Button b12(1170, 140, 115, 35, "过程展示");
		if (b1.button()) {
			pathcount = 0;  // 路径计数器重置为0
			word.clear();   // 清空单词（word）字符串
			// 地图生成
			for (int i = 0; i < N; i++) {
				li[i].clear();  // 清空列表li中的所有元素
			}
			for (int i = 0; i < N; i++) {
				lowlist[i].clear();  // 清空lowlist中的所有元素
			}
			for (int i = 0; i < N; i++) {
				alllist[i].clear();  // 清空alllist中的所有元素
			}
			int x = rand() % (min(WIDTH, HEIGHT) / 5) + 10;  // 生成一个随机整数x，其值介于WIDTH和HEIGHT的最小值除以5加上10

			BLOCK_XY = x;  // BLOCK_XY的值设置为x
			BLOCK_WIDTH = WIDTH / x -1, BLOCK_HEIGHT = HEIGHT / x -1;  // 计算BLOCK_WIDTH为WIDTH除以x，BLOCK_HEIGHT为HEIGHT除以x
			cleardevice();  // 清除设备
			w.init();  // 初始化w
			w.display();  // 显示w
			w.copy();  // 复制w
			ff = true;  // 将ff设置为true
			ispt = false;
			i = -1;  // 初始化i为-1
			isdoneb12 = false;
		}

		if (b2.button()) {
			pathcount = 0;  // 路径计数器重置为0
			word.clear();  // 清空单词（word）字符串
			// 地图生成
			for (int i = 0; i < N; i++) {
				li[i].clear();  // 清空列表li中的所有元素
			}
			for (int i = 0; i < N; i++) {
				lowlist[i].clear();  // 清空lowlist中的所有元素
			}
			for (int i = 0; i < N; i++) {
				alllist[i].clear();  // 清空alllist中的所有元素
			}
			bool f = false;
			char s[M];
			InputBox(s, 1000, "请输入文件名称，不超过100词");

			for (int i = 0; i < strlen(s); i++) {
				if (s[i] == '.') {
					f = true;
				}
			}

			if (!f) {
				// 错误处理
				HWND hwn = GetHWnd();
				MessageBox(hwn, "输入非法，请重新输入", "警告", MB_OKCANCEL);
			}

			w.rd(s);  // 从文件中读取数据到w
			cleardevice();  // 清除设备
			w.display();  // 显示w
			isdoneb12 = false;
			f = true;  // 设置f为true
			i = -1;  // 初始化i为-1
		}

		if (b3.button()) {
			if (!endx || !endy) {
				// 提示用户设置起点或终点
				HWND hwn = GetHWnd();
				MessageBox(hwn, "你还没有设置起点或终点", "警告", MB_OKCANCEL);
			}
			else if (!isdoneb12) {
				HWND hwn = GetHWnd();
				MessageBox(hwn, "你没有按过程展示和直接展示按钮", "警告", MB_OKCANCEL);
			}
			else {
				word.clear();  // 清空单词（word）字符串

				pathcount = 0;  // 路径计数器重置为0
				// 全部清空
				memset(vis, 0, sizeof vis);
				memset(pre, -1, sizeof pre);
				memset(preD, -1, sizeof preD);
				vis[sax][say] = true;
				dfs(sax, say);  // 深度优先搜索
				w.display();  // 显示w
			}
			i = 0;  // 设置i为0
		}

		if (b4.button()) {
			if (!endx || !endy) {
				// 提示用户设置起点或终点
				HWND hwn = GetHWnd();
				MessageBox(hwn, "你还没有设置起点或终点", "警告", MB_OKCANCEL);
			}
			else {
				pathcount = 0;  // 路径计数器重置为0
				word.clear();  // 清空单词（word）字符串
				int k = A_start(sax, say, endx, endy);  // 执行A*算法
				print(endx, endy, false, false);  // 打印终点坐标
				w.display();  // 显示w
			}
			i = 1;  // 设置i为1
		}

		if (b5.button()) {
			if (!(!sax && !say)) {
				w.setw(sax, say, w.getg(sax, say));  // 设置坐标(sax, say)的值为START
			}
			bool f = false;
			char s[N];
			InputBox(s, 100, "请输入x坐标");
				// 将用户输入转换为数字
			sax = 0;
			for (int i = 0; i < strlen(s); i++) {
				if (s[i] >= '0' && s[i] <= '9') {
					sax = sax * 10 + s[i] - '0';
				}
				else {
					f = true;
				}
			}

			if (f || sax<1 || sax>BLOCK_WIDTH) {
				// 错误处理
				HWND hwn = GetHWnd();
				MessageBox(hwn, "输入非法，请重新输入", "警告", MB_OKCANCEL);
				continue;
			}

			memset(s, 0, sizeof s);
			InputBox(s, 100, "请输入y坐标");

			// 将用户输入转换为数字
			say = 0;
			for (int i = 0; i < strlen(s); i++) {
				if (s[i] >= '0' && s[i] <= '9') {
					say = say * 10 + s[i] - '0';
				}
				else {
					f = true;
				}
			}

			if (f || say<1 || say>BLOCK_HEIGHT) {
				// 错误处理
				HWND hwn = GetHWnd();
				MessageBox(hwn, "输入非法，请重新输入", "警告", MB_OKCANCEL);
				continue;
			}
			w.setw(sax, say, START);  // 设置坐标(sax, say)的值为START
			w.display();  // 显示w
			ispt = false;
		}
		if (b6.button()) {
			// 按钮b6被按下时的处理

			// 如果终点坐标不为空
			if (!(!endx && !endy)) {
				// 将终点坐标设置为当前位置的状态
				w.setw(sax, say, w.getg(sax, say));
			}

			// 循环直到用户输入有效的x坐标
			bool f = false; // 标记输入是否合法
			char s[N]; // 存储用户输入的字符串
			InputBox(s, 100, "请输入x坐标");

			// 将用户输入转换为数字
			endx = 0;
			for (int i = 0; i < strlen(s); i++) {
				if (s[i] >= '0' && s[i] <= '9') {
					endx = endx * 10 + s[i] - '0';
				}
				else {
					f = true; // 标记输入非法
				}
			}

			// 如果输入非法或者超出范围，弹出警告框
			if (f || endx < 1 || endx > BLOCK_WIDTH) {
				HWND hwn = GetHWnd();
				MessageBox(hwn, "输入非法，请重新输入", "警告", MB_OKCANCEL);
				continue;
			}
			i = -1; // 重置计数器

			// 循环直到用户输入有效的y坐标
			memset(s, 0, sizeof s);
			InputBox(s, 100, "请输入y坐标");

			// 将用户输入转换为数字
			endy = 0;
			for (int i = 0; i < strlen(s); i++) {
				if (s[i] >= '0' && s[i] <= '9') {
					endy = (endy << 3) + (endy << 1) + s[i] - '0';
				}
				else {
					f = true; // 标记输入非法
				}
			}

			// 如果输入非法或者超出范围，弹出警告框
			if (f || endy < 1 || endy > BLOCK_HEIGHT) {
				HWND hwn = GetHWnd();
				MessageBox(hwn, "输入非法，请重新输入", "警告", MB_OKCANCEL);
				continue;
			}

			// 将终点坐标设置为FINISH状态，并显示更新后的迷宫
			w.setw(endx, endy, FINISH);
			w.display();
			ispt = false;
			i = -1; // 重置计数器
		}

		if (b7.button()) {
			// 按钮b7被按下时的处理

			ispt = false;
			// 清空数据和状态
			word.clear();
			cleardevice();
			pathcount = 0;
			for (int i = 0; i < N; i++) {
				li[i].clear();
			}
			for (int i = 0; i < N; i++) {
				lowlist[i].clear();
			}
			for (int i = 0; i < N; i++) {
				alllist[i].clear();
			}
			i = -1;

			// 将起点和终点坐标设置为初始状态
			w.setw(sax, say, w.getg(sax, say));
			w.setw(endx, endy, w.getg(endx, endy));
			sax = say = endx = endy = 0;

			// 显示清空成功的提示框
			HWND hwn = GetHWnd();
			MessageBox(hwn, "清空成功", "提示", MB_OKCANCEL);

			ff = true;
			isdoneb12 = false;
			isfind = false;
			w.display();
		}

		if (b8.button()) {
			// 按钮b8被按下时的处理

			// 清空数据和状态
			word.clear();
			bool f = false;
			char s[N];
			ispt = false;

			// 提示用户输入迷宫宽度（格数）
			InputBox(s, 100, "请输入迷宫的宽度（单位格数）");

			// 将用户输入的宽度转换为数字
			int ans = 0;
			for (int i = 0; i < strlen(s); i++) {
				if (s[i] >= '0' && s[i] <= '9') {
					ans = (ans << 3) + (ans << 1) + s[i] - '0';   
				}
				else {
					f = true; // 标记输入非法
				}
			}

			// 如果输入非法或者超出范围，弹出警告框
			if (f || ans <= 0 || ans > 80) {
				HWND hwn = GetHWnd();
				MessageBox(hwn, "输入非法，请重新输入", "警告", MB_OKCANCEL);
				continue; // 回到循环开始处
			}

			// 提示用户输入迷宫高度（格数）
			InputBox(s, 100, "请输入迷宫的高度（单位格数）");

			// 将用户输入的高度转换为数字
			int ans1 = 0;
			for (int i = 0; i < strlen(s); i++) {
				if (s[i] >= '0' && s[i] <= '9') {
					ans1 = ans1 * 10 + s[i] - '0';
				}
				else {
					f = true; // 标记输入非法
				}
			}

			// 如果输入非法或者超出范围，弹出警告框
			if (f || ans1 <= 0 || ans1 > 80) {
				HWND hwn = GetHWnd();
				MessageBox(hwn, "输入非法，请重新输入", "警告", MB_OKCANCEL);
				continue; // 回到循环开始处
			}

			// 清空数据和状态
			for (int i = 0; i < N; i++) {
				li[i].clear();
			}
			for (int i = 0; i < N; i++) {
				lowlist[i].clear();
			}
			for (int i = 0; i < N; i++) {
				alllist[i].clear();
			}
			i = -1;

			// 将起点和终点坐标设置为初始状态
			w.setw(sax, say, w.getg(sax, say));
			w.setw(endx, endy, w.getg(endx, endy));

			// 清空屏幕并重新设置迷宫参数
			cleardevice();
			BLOCK_WIDTH = ans, BLOCK_HEIGHT = ans1;
			BLOCK_XY = min(WIDTH / ans, HEIGHT / ans1)+1;
			w.init();
			w.display();
			isfind = false;
			isdoneb12 = false;
			f = true; // 标记迷宫已生成
		}

		if (b9.button()) {
			// 按钮b9被按下时的处理

			i = -1; // 重置计数器

			// 如果迷宫尚未生成，弹出警告框
			if (!f) {
				HWND hwn = GetHWnd();
				MessageBox(hwn, "你还没有生成迷宫", "警告", MB_OKCANCEL);
				continue; // 回到循环开始处
			}

			// 开始寻路
			w.wd();
			isdoneb12 = false;
		}

		if (b10.button()) {
			if (ispt) {
				HWND hwn = GetHWnd();
				tempword = word;

				print(endx, endy, false, true);
			}
			else {
				HWND hwn = GetHWnd();
				MessageBox(hwn, "路径尚未生成", "警告", MB_OKCANCEL);
			}
		}


		if (b11.button()) {
			isfind = false;
			isdoneb12 = true;
		}

		if (b12.button()) {
			isfind = true;
			isdoneb12 = true;
		}


		EndBatchDraw();
		msg.message = 0;
	}
}

// dfs查找所有路径
void dfs(int sx, int sy) {
	// 如果到达终点，打印所有路径并展示动画
	if (sx == endx && sy == endy) {
		ispt = true;
		print(sx, sy, true, false); // 打印路径
		if (isfind) {
			w.display(); // 显示路径
			Sleep(1000); // 等待2秒钟
			w.display2(); // 再次显示路径
		}
		return;
	}

	// 尝试向四个方向递归查找路径
	for (int i = 0; i < 4; i++) {
		int a = dx[i] + sx, b = dy[i] + sy;

		// 检查边界和障碍物
		if (a < 1 || b < 1 || a > BLOCK_WIDTH || b > BLOCK_HEIGHT || vis[a][b] || w.getw(a,b) == WALL)
			continue;

		// 标记访问状态，记录路径
		vis[a][b] = true;
		pre[a][b] = { sx, sy };
		li[a][b]++;
		if(isfind){
			w.display2(); // 展示dfs递归过程，即动画效果
			Sleep(10);
		}
		dfs(a, b); // 递归调用dfs
		vis[a][b] = false;
		// 取消路径记录，展示动画
		li[a][b]--;
		if (isfind) {
			w.display2();
			Sleep(10);
		}
	}
}
//A*寻路

void print(int s, int t, bool f,bool isbutton) {
	// 根据f变量判断是A*算法还是DFS，以便使用不同的颜色标记路径
	vector<pair<int, int>> path;
	int x = s, y = t;

	// 构建路径
	while (x != -1 && y != -1) {
		path.push_back({ x, y });
		tie(x, y) = pre[x][y]; // 根据预设的路径数组回溯路径
	}

	reverse(path.begin(), path.end()); // 路径反转，因为是从终点往起点回溯的

	char b[M] = { 0 }; // 存放路径信息的字符数组
	char cnm[M] = { 0 }; // 存放路径信息的字符数组
	int cnt = 0; // 路径节点计数
	if (!isbutton) {
		pathcount++;
		word += " 路径 ";
		word += to_string(pathcount);
		word += "： ";
	}
	// 遍历路径并输出到屏幕
	for (auto t : path) {
		if (!isbutton) {
			if (f) {
				lowlist[t.first][t.second]++; // 更新路径上的节点信息（用于DFS）
			}
			else {
				alllist[t.first][t.second]++; // 更新路径上的节点信息（用于A*算法）
			}
			cnt++;
			// 构造输出字符串
			word += "(";
			word += to_string(t.first);
			word += ",";
			word += to_string(t.second);
			word += ") ";
			if (cnt != path.size()) {
				word += "->";
			}

			// 将路径信息复制到字符数组b中
			for (int i = 0; i < word.size(); i++) {
				b[i] = word[i];
			}

			drawtext(b, &r, DT_WORDBREAK | DT_WORD_ELLIPSIS); // 调用绘制函数显示路径信息
			w.display(); // 更新屏幕显示

		}

	}

	
	char c[] = "无任何路径"; // 默认显示的路径不存在信息
	if (cnt == 1) {
		drawtext(c, &r, DT_WORDBREAK| DT_WORD_ELLIPSIS); // 如果路径节点计数为1，则显示路径不存在信息
		return;
	}


	if (isbutton) {
		HWND hwn = GetHWnd();

		for (int i = 0; i < word.size(); i++) {
			cnm[i] = word[i];
		}

		MessageBox(hwn, cnm, "所有路径", MB_OKCANCEL);
	}
	else {
		word += '\n';
		word += "-----------------------------------------------------------------------------------------------------";
		word += '\n';
		// 将路径信息复制到字符数组b中
		for (int i = 0; i < word.size(); i++) {
			b[i] = word[i];
		}

		drawtext(b, &r, DT_WORDBREAK | DT_WORD_ELLIPSIS); // 调用绘制函数显示路径信息
		w.display(); // 更新屏幕显示
	}


}

int f(int sx, int sy, int ex, int ey) {
	// 曼哈顿距离作为启发函数（估价函数）
	return abs(sx - ex) + abs(sy - ey);
}

int A_start(int sx, int sy, int ex, int ey) {
	// A*算法的主体部分

	priority_queue<E> q; // 优先队列，用于实现A*算法的优先级搜索

	memset(dist, 0x3f, sizeof dist); // 初始化距离数组，将所有距离设置为无穷大
	dist[sx][sy] = 0; // 起点到自身的距离设置为0
	memset(st, 0, sizeof st); // 初始化状态数组，用于标记节点是否已被访问过
	memset(pre, -1, sizeof pre); // 初始化路径数组，用于记录每个节点的前驱节点

	q.push({ f(sx, sy, ex, ey), dist[sx][sy], sx, sy }); // 将起点加入优先队列，优先级为启发函数值

	while (!q.empty()) {
		E t = q.top(); // 取出当前优先级最高的节点
		q.pop();

		int x = t.x, y = t.y, d = t.r; // 获取节点的坐标及到起点的距离

		if (st[x][y]) { // 如果该节点已被访问过，则跳过
			continue;
		}
		st[x][y] = true; // 标记该节点为已访问

		if (x == ex && y == ey) { // 如果当前节点为终点，则返回到达终点的距离
			ispt = true;
			return d;
		}

		// 遍历当前节点的相邻节点
		for (int i = 0; i < 4; i++) {
			int a = dx[i] + x, b = dy[i] + y; // 计算相邻节点的坐标
			if (a < 1 || b < 1 || a > BLOCK_WIDTH || b > BLOCK_HEIGHT || st[a][b] || w.getw(a,b) == WALL) {
				continue; // 如果相邻节点不符合条件，则跳过
			}
			if (dist[a][b] > d + 1) {
				q.push({ f(a, b, ex, ey) + d + 1, d + 1, a, b }); // 更新相邻节点的距离和优先级，并加入优先队列
				pre[a][b] = { x, y }; // 记录相邻节点的前驱节点
				dist[a][b] = d + 1; // 更新到起点的距离
			}
		}
	}
}